package com.bluebridgecup.SearchBasics;


import java.util.Scanner;

public class dfs实现排列型枚举 {
    // 定义一个布尔类型的数组，用于标记数字是否已经在当前排列中使用过
    static boolean[] a;
    // 定义一个整数变量n，表示要生成全排列的数字范围是从1到n
    static int n;
    // 定义一个整数类型的数组b，用于存储当前正在生成的排列
    static int[] b;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取一个整数，并赋值给n
        n = in.nextInt();
        // 初始化布尔类型数组a，长度为n+1，初始值都为false，表示所有数字都未被使用
        a = new boolean[n + 1];
        // 初始化整数数组b，数组长度为n+1，用于存储排序
        b = new int[n + 1];
        // 调用深度优先搜索函数dfs，从第1个位置开始生成排序
        dfs(1);
    }

    // 定义深度优先搜索函数dfs，x表示当前要填充的位置
    static void dfs(int x) {
        // 如果当前要填充的位置x大于n，表示已经生成了一个完整的排列
        if (x > n) {
            // 遍历数组b，输出当前排列中的每个数字，数字之间用空格分隔开
            for (int i = 1; i <= n; i++) {
                System.out.print(b[i] + " ");
            }
            // 输出换行符，准备输出下一个排列
            System.out.println();
            // 返回上一层递归
            return;
        }
        // 尝试将1到n中的每个数字填入当前位置x
        for (int i = 1; i <= n; i++) {
            // 如果数字i还未被使用
            if (!a[i]) {
                // 标记数组i已经被使用
                a[i] = true;
                // 将数字i填入数组b的第x个位置
                b[x] = i;
                // 递归调用dfs函数，填充下一个位置x+1
                dfs(x + 1);
                // 回溯操作，将数字i标记为未使用，以便尝试其它肯的排列
                a[i] = false;
            }
        }
    }
}
